#include <bits/stdc++.h>

using namespace std;

// 会议必须独占时间段的最大会议数量
// 给定若干会议的开始、结束时间
// 你参加某个会议的期间，不能参加其他会议
// 返回你能参加的最大会议数量
// 来自真实大厂笔试，没有在线测试，对数器验证
// 测试链接：https://www.luogu.com.cn/problem/P1803

// 把所有会议全排列
// 其中一定有安排会议次数最多的排列
int f(vector<vector<int>>& meeting, int n, int i)
{
    int ans = 0;
    if(i == n)
    {
        for(int j = 0, time = -1; j < n; ++j)
        {
            if(time <= meeting[j][0])
            {
                ++ans;
                time = meeting[j][1];
            }
        }
    }
    else
    {
        for(int j = i; j < n; ++j)
        {
            swap(meeting[i], meeting[j]);
            ans = max(ans, f(meeting, n, i + 1));
            swap(meeting[i], meeting[j]);
        }
    }
    return ans;
}

// 暴力方法
// 为了验证
// 时间复杂度O(n!)
int maxMeeting1(vector<vector<int>>& meeting)
{
    return f(meeting, meeting.size(), 0);
}

// 正式方法
// 时间复杂度O(n*logn)
int maxMeeting2(vector<vector<int>>& meeting)
{
    // meeting[i][0] : i号会议开始时间
    // meeting[i][1] : i号会议结束时间
    sort(meeting.begin(), meeting.end(), [](auto& a, auto& b){
        return a[1] < b[1];
    });
    int n = meeting.size(), ans = 0;
    for(int i = 0, cur = -1; i < n; ++i)
    {
        if(cur <= meeting[i][0])
        {
            ++ans;
            cur = meeting[i][1];
        }
    }
    return ans;
}

// 为了验证
// 生成随机会议
vector<vector<int>> randomMeeting(int n, int m)
{
    vector<vector<int>> ans(n, vector<int>(2));
    for(int i = 0, a, b; i < n; ++i)
    {
        a = rand() % m;
        b = rand() % m;
        if(a == b)
        {
            ans[i][0] = a;
            ans[i][1] = a + 1;
        }
        else
        {
            ans[i][0] = min(a, b);
            ans[i][1] = max(a, b);
        }
    }
    return ans;
}

int main()
{
	// 对数器
	// 为了验证
    srand(time(nullptr));
    int N = 10;
    int M = 12;
    int testTimes = 2000;
    cout << "测试开始" << endl;
    for(int i = 1; i <= testTimes; ++i)
    {
        int n = rand() % N + 1;
        vector<vector<int>>&& meeting = randomMeeting(n, M);
        int ans1 = maxMeeting1(meeting);
        int ans2 = maxMeeting2(meeting);
        if(ans1 != ans2)
        {
            // 如果出错了
            // 可以增加打印行为找到一组出错的例子
            // 然后去debug
            cout << "出错了！" << endl;
        }
        if(i % 100 == 0)
        {
            cout << "(测试到第" << i << "组)" << endl;
        }
    }
    cout << "测试结束" << endl;

    return 0;
}